Kebingungan Rantai Pasok 📉
Kapal-kapal tiba dalam urutan yang acak. Kita perlu menghitung Metrik Kebingungan (jumlah inversi) untuk mengoptimalkan pengendali lalu lintas AI.
Apa Itu Inversi?
Sebuah pasangan indeks $(i, j)$ disebut inversi jika:
- $i < j$ (Kapal $i$ tiba sebelum $j$)
- $A[i] > A[j]$ (Kapal $i$ memiliki ID prioritas yang lebih tinggi)
Analisis 🔍
Urutan Contoh: [2, 4, 1, 3, 5]
- ❌ (2, 1): 2 datang sebelum 1, tetapi 2 > 1
- ❌ (4, 1): 4 datang sebelum 1, tetapi 4 > 1
- ❌ (4, 3): 4 datang sebelum 3, tetapi 4 > 3
- Kebingungan Total: 3 Inversi
Tantangan
Pendekatan brute force dengan loop bersarang adalah $O(N^2)$.
for i in range(n):
for j in range(i+1, n): ...
for j in range(i+1, n): ...
Untuk $N=100.000$, ini membutuhkan sekitar 10 miliar operasi. Hasil: Melebihi Batas Waktu.